//堆排序
//首先理解什么是堆：
//大顶堆：根节点的值>=子结点的值的完全二叉树
//小顶堆：根节点的值<=子结点的值的完全二叉树

//完全二叉树：将根节点的下标视为0，则有：
//（1）完全二叉树中第i个数，左子节点下标left = 2i+1
// (2)完全二叉树中第i个数，右子节点下标right = 2i+2 = left+1
// 对于有n个元素的完全二叉树，它的最后一个非叶子节点的下标为 n/2 -1
// 可以用BFS来理解

//堆排序可以实现升序或者降序的排序。如果是升序，则构造大顶堆；如果是降序，则构造小顶堆
//https://www.cnblogs.com/chengxiao/p/6129630.html

//初始化堆的时间复杂度为O(n)，重建堆的时间复杂度为O(nlogn)，因此总时间复杂度为O(nlogn)。空间复杂度为O(1)。
//是一种不稳定的排序。

//大顶堆小顶堆的实现可以使用PriorityQueue。

public class heapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{6,2,1,3,5,4};
        heapSort(arr);
        for(int i = 0 ; i < 6 ; i++){
            System.out.println(arr[i]);
        }
    }

    //堆排序，升序
    public static void heapSort(int[] arr) {

        //整个流程：
        //用n个数构造初始大顶堆
        //将堆顶最大的元素（第一个元素）与最后一个元素交换位置，堆的规模-1
        //保持第n个元素为最大的数，在前n-1个数中重新调整构建大顶堆，重复以上过程
        //当堆的规模已到达最小时，终止，得到升序序列

        // 构建初始大顶堆
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            // 将最大值放到数组最后
            exchange(arr, 0, i);
            // 调整剩余数组，使其满足大顶堆
            maxHeapify(arr, 0, i);
        }
    }

    // 构建初始大顶堆
    public static void buildMaxHeap(int[] arr) {
        // 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }
    }

    // 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
    private static void maxHeapify(int[] arr, int i, int heapSize) {
        // 左子结点下标
        int l = 2 * i + 1;
        // 右子结点下标
        int r = l + 1;
        // 记录根结点、左子树结点、右子树结点三者中的最大值下标
        int largest = i;

        // 下面这一串就是为了找到根左右三个节点中的最大值，并且与根节点的值交换，构造大顶堆
        // 与左子树结点比较
        if (l < heapSize && arr[l] > arr[largest]) {
            largest = l;
        }
        // 与右子树结点比较
        if (r < heapSize && arr[r] > arr[largest]) {
            largest = r;
        }
        if (largest != i) {
            // 将最大值交换为根结点
            exchange(arr, i, largest);
            // 再次调整交换数字后的大顶堆
            // 因为保证了根节点值最大以后，较小的值被移到子节点的位置，则会对结构再次造成影响，所以还要递归向下调整
            maxHeapify(arr, largest, heapSize);
        }
    }
    // 交换元素
    private static void exchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
